package com.desin.modle.datastruct.algo.DynamicAlgorithm.zeroOnePackage;

import com.desin.modle.datastruct.listnode.ListNode;
import com.desin.modle.datastruct.tree.BinarySearchTree;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class SolutionZerOne {
    public int test(int[] items,int maxNum,int maxWeight){
        boolean[][] status = new boolean[maxNum][maxWeight+1];
        status[0][0]=true;
        status[0][items[0]]=true;
        for(int i=1;i<maxNum;i++){
            for(int j=0;j<=maxWeight;j++){
                if(status[i-1][j]){
                    status[i][j]=true;
                }
            }
            for(int j=0;j<=maxWeight-items[i];j++){
                if(status[i-1][j]){
                    status[i][j+items[i]]=true;
                }
            }
        }
        for(int i=maxWeight;i>=0;i--){
            if(status[maxNum-1][i]){
                return i;
            }
        }
        return 0;
    }

    public int jisuanMaxValues(int[] weights,int[] values,int maxNum,int maxWeight){
        int[][] status = new int[maxNum][maxWeight+1];
        for(int i=0;i<maxNum;i++){
            for(int j=0;j<=maxWeight;j++){
                status[i][j]=-1;
            }
        }
        status[0][0]=0;
        status[0][weights[0]]=values[0];
        for(int i=1;i<maxNum;i++){
            for(int j=0;j<=maxWeight;j++){
                if(status[i-1][j]>=0){
                    status[i][j]=status[i-1][j];
                }
            }
            for(int j=0;j<=maxWeight-weights[i];j++){
                if(status[i-1][j]>=0){
                    int newValue = status[i-1][j]+values[i];
                    if(newValue>status[i][j+weights[i]]){
                        status[i][j+weights[i]]=newValue;
                    }
                }
            }
        }
        int resValue = -1;
        for(int i=0;i<=maxWeight;i++){
            if(status[maxNum-1][i]>resValue){
                resValue=status[maxNum-1][i];
            }
        }
        return resValue;
    }

    public int findMaxLengthXuLie(int[] nums){
        if(nums==null||nums.length==0){
            return 0;
        }
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp,1);
        int maxLength = 1;
        for(int i=1;i<n;i++){
            if(nums[i]>nums[i-1]){
                dp[i]=dp[i-1]+1;
                maxLength = Math.max(dp[i],maxLength);
            }
        }
        return maxLength;
    }

    public int findMaxLengthXl(int[] nums){
        if(nums==null||nums.length==0){
            return 0;
        }
        int n=nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp,1);
        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                if(nums[j]<nums[i]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
        }
        int res =1;
        for(int i=0;i<n;i++){
            res = Math.max(dp[i],res);
        }
        return res;
    }

    public int findMaxLengthX2(int[] nums){
        if(nums==null||nums.length==0){
            return 0;
        }
        Arrays.sort(nums);
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp,1);
        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                if(nums[i]==nums[j]+1){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
        }
        int res =1;
        for(int a:dp){
            res = Math.max(res,a);
        }
        return res;
    }

    public int maxProduct(int[] nums){
        if(nums==null||nums.length==0){
            return 0;
        }
        if(nums.length==1){
            return nums[0];
        }
        int n = nums.length;
        int[] maxDp = new int[n];
        int[] minDp = new int[n];
        maxDp[0]=nums[0];
        minDp[0]=nums[0];
        for(int i=1;i<n;i++){
            maxDp[i]=Math.max(maxDp[i-1]*nums[i],Math.max(minDp[i-1]*nums[i],nums[i]));
            minDp[i]=Math.min(minDp[i-1]*nums[i],Math.min(maxDp[i-1]*nums[i],nums[i]));
        }
        int res = Integer.MIN_VALUE;
        for(int a:maxDp){
            res = Math.max(res,a);
        }
        return res;
    }

    public int maxDaJia(int[] nums){
        if(nums==null||nums.length==0){
            return 0;
        }
        if(nums.length==1){
            return nums[0];
        }
        int[] dp = new int[nums.length];
        dp[0]=nums[0];
        dp[1]=Math.max(nums[0],nums[1]);
        for(int i=2;i<nums.length;i++){
            dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]);
        }
        return dp[nums.length-1];
    }

    public int maxDaJiaTree(BinarySearchTree.TreeNode root){
        int[] res = dfs(root);
        return Math.max(res[0],res[1]);
    }

    private int[] dfs(BinarySearchTree.TreeNode root) {
        if(root==null){
            return new int[]{0,0};
        }
        int[] leftRes = dfs(root.getLeft());
        int[] rightRes = dfs(root.getRight());
        int contains = leftRes[1]+rightRes[1]+root.getVal();
        int noContains = Math.max(leftRes[0],leftRes[1])+Math.max(rightRes[0],rightRes[1]);
        return new int[]{contains,noContains};
    }

    public int maxGuPiao(int[] nums){
        if(nums==null||nums.length<2){
            return 0;
        }
        int minPrice = nums[0];
        int[] dp = new int[nums.length];
        for(int i=1;i<nums.length;i++){
            minPrice = Math.min(minPrice,nums[i]);
            dp[i]=Math.max(dp[i-1],nums[i]-minPrice);
        }
        return dp[nums.length-1];
    }

    int maxSize = 0;
    public int treeZhiJin(BinarySearchTree.TreeNode root){
        treeZhiJinHelper(root);
        return maxSize;
    }

    private int treeZhiJinHelper(BinarySearchTree.TreeNode root) {
        if(root==null){
            return 0;
        }
        int leftSize = treeZhiJinHelper(root.getLeft());
        int rightSize = treeZhiJinHelper(root.getRight());
        maxSize = Math.max(maxSize,leftSize+rightSize);
        return Math.max(leftSize,rightSize)+1;
    }
    int maxValue = Integer.MIN_VALUE;
    public int maxPathSum(BinarySearchTree.TreeNode root){
        maxPathSumHelper(root);
        return maxValue;
    }

    private int maxPathSumHelper(BinarySearchTree.TreeNode root) {
        if(root==null){
            return 0;
        }
        int leftValue = Math.max(maxPathSumHelper(root.getLeft()),0);
        int rightValue = Math.max(maxPathSumHelper(root.getRight()),0);
        maxValue= Math.max(maxValue,leftValue+rightValue+root.getVal());
        return root.getVal()+Math.max(leftValue,rightValue);
    }

    public int pathSum(BinarySearchTree.TreeNode root, int targetSum) {
        if(root==null){
            return 0;
        }
        int result = pathSumHelper(root,targetSum);
        int leftRes = pathSum(root.getLeft(),targetSum);
        int rightRes= pathSum(root.getRight(),targetSum);
        return result+leftRes+rightRes;
    }
    public int pathSumHelper(BinarySearchTree.TreeNode root, int targetSum){
        if(root==null){
            return 0;
        }
        int res = root.getVal()==targetSum?1:0;
        int leftRes = pathSumHelper(root.getLeft(),targetSum-root.getVal());
        int rightRes = pathSumHelper(root.getRight(),targetSum-root.getVal());
        return res+leftRes+rightRes;
    }

    public int[] tagertSum(int[] nums,int target){
        Map<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<nums.length;i++){
            if(map.containsKey(target-nums[i])){
                return new int[]{i,map.get(target-nums[i])};
            }else{
                map.put(nums[i],i);
            }
        }
        return null;
    }

    public ListNode reverseNode(ListNode node){
        ListNode p = null;
        ListNode cur = node;
        while(cur!=null){
            ListNode temp = cur.next;
            cur.next=p;
            p=cur;
            cur=temp;
        }
        return p;
    }

}
